#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std ;

const int maxn = 510 ;  //图的点数最大值

int n , m ; //n 是点数  ， m 是边数
int g[maxn][maxn] ; //临界举矩阵
int dist[maxn] ;    //没个点的最短距离
bool st[maxn] ;     //这个点是不是已经确定了最短距离 --> S 集合

int dijkstra() {
    memset(dist , 0x3f , sizeof dist) ;
    dist[1] = 0 ;   //初始化所有点的距离为 无穷 这里就说明了从下标 1 的地方开始存

    for (int i = 0; i < n; ++i) {   //这里从 0 开始遍历是因为循环 n 次，从 1 开始也一样
        //遍历所有点
        int t = -1 ;    //初始化 t 为一个不存在的数
        //找到没有确定最短路的点中长度最短的一个
        for(int j = 1 ; j <= n ; j ++ ){    //这里从1 开始遍历
            if(!st[j] && (t == -1 || dist[t] > dist[j])) {
                //如果当前这个点没被找过
                //t = -1 表示 t 还没被确定 ， 这时候总要给他赋一个值 , 所以让 t = j
                //dist[t] > dist[j] 表示 t 这个点不是最短的
                t = j ;
            }
        }

        st[t] = true ;

        //更新其他点的距离
        for (int k = 1; k <= n; ++k) {  //从 1 开始是因为是从 1 开始存的
            dist[k] = min(dist[k] , dist[t] + g[t][k]);
        }
    }

    if(dist[n] == 0x3f3f3f3f) {
        return -1 ;
    }
    return dist[n];
}


int  main() {

    scanf("%d%d" , &n , &m);

    memset(g ,  0x3f , sizeof g);    //初始化所有点的距离为最大值

    while(m--) {
        //输入邻接矩阵    有自环和重边的 ， 自环不用管 ， 重边的话保留权值最小的那条边  ，
        int a , b , c ;
        scanf("%d%d%d" , &a , &b , &c) ;    //a , b 表示边的顶点 ，c表示边的权值
        g[a][b] = min(g[a][b] , c);
    }

    int t = dijkstra();

    printf("%d\n" , t);

    return 0 ;
}
